﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;

//int main()
//{
//	vector<int> v = { 22, 8, 57, 41, 36, 46, 42, 28, 42, 14, 9, 43,
//		27, 51, 0, 0, 38, 50, 31, 60, 29, 31, 20, 23, 37, 53, 27,
//		1, 47, 42, 28, 31, 10, 35, 39, 12, 15, 6, 35, 31, 45, 21,
//		30, 19, 5, 5, 4, 18, 38, 51, 10, 7, 20, 38, 28, 53, 15, 55,
//		60, 56, 43, 48, 34, 53, 54, 55, 14, 9, 56, 52 };
//	vector<int> vs;
//	vs.push_back(22);
//	for (int i = 1; i < v.size(); i++)
//	{
//		auto it = find(vs.begin(), vs.end(), v[i]);
//		if (it == vs.end()) vs.push_back(v[i]);
//	}
//	cout << '[';
//	for (int e : vs) cout << e << ',';
//	cout << ']';
//	return 0;
//}

//int main()
//{
//    vector<int> nums = { 31,27,31,35,39 };
//        int n = nums.size();
//        if (n < 3) return n;
//        vector<vector<int>> dp(n, vector<int>(n));
//        int maxlen = 2;
//
//        //cout << "1 2 ";
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = 1; j < i; j++)
//            {
//                if (i == n - 1 && j == i - 1)
//                {
//                    cout << "最后一次" << endl;
//                }
//                int ret = nums[j] - (nums[i] - nums[j]);
//                auto it = find(nums.begin(), nums.begin() + j, ret);
//                if (it != nums.begin() + j)
//                {
//                    int k = it - nums.begin();
//                    dp[j][i] = max(dp[k][j] + 1, 3);
//                    maxlen = max(maxlen, dp[j][i]);
//                }
//                cout << dp[j][i] << ' ';
//            }
//            cout << endl;
//            //cout << maxlen << ' ';
//        }
//        return 0;
//};

//class Solution {
//public:
//    int longestArithSeqLength(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 3) return n;
//        vector<vector<int>> dp(n, vector<int>(n, 2));
//        unordered_map<int, int> hash = { {nums[0], 0} };
//        int maxlen = 2;
//
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = 1; j < i; j++)
//            {
//                int ret = nums[j] - (nums[i] - nums[j]);
//                if (hash.find(ret) != hash.end())
//                {
//                    int k = hash[ret];
//                    dp[j][i] = dp[k][j] + 1;
//                    maxlen = max(maxlen, dp[j][i]);
//                }
//                hash[nums[j]] = j;
//            }
//            hash.clear();
//            hash[nums[0]] = 0;
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums) {
//        int n = nums.size();
//        int count = 0;
//        unordered_map<long long, vector<int>> hash;
//        vector<vector<int>> dp(n, vector<int>(n));
//
//        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
//
//        for (int i = 2; i < n; i++)
//        {
//            for (int j = 1; j < i; j++)
//            {
//                long long ret = (long long)2 * nums[j] - nums[i];
//                if (hash.find(ret) != hash.end())
//                {
//                    for (int k : hash[ret])
//                    {
//                        if (k < j)
//                        {
//                            dp[j][i] += dp[k][j] + 1;
//                            //  count += dp[j][i];
//                        }
//                    }
//                }
//                count += dp[j][i];
//            }
//        }
//        return count;
//    }
//};


